package com.s4.queue;

public class LinkedQueue implements IQueue {
	
	private static class Node {
		public Object data;
		public Node next;
	}
	
	protected static final int DEFAULT_LENGTH = 10;
	
	// head 指向队尾，tail表示队尾下标
	protected Node head = null;
	protected Node tail = head;
	
	// 预设长度
	private final int presetLength;
	private int length = 0;
	
	public LinkedQueue() {
		this(DEFAULT_LENGTH);
	}
	
	public LinkedQueue(int value) {
		this.presetLength = value;
	}
	
	// 队列的已用空间的长度
	public int getLength() {
		return this.length;
	}
	
	@Override
	public int getPresetLength() {
		return this.presetLength;
	}
	
	// 入队操作
	public boolean enqueue(Object value) {
		if (this.isFull()) {
			return false;
		}
		Node node = new Node();
		node.data = value;
		node.next = null;
		if (this.isEmpty()) {
			this.head = node;
		} else {
			this.tail.next = node;
		}
		this.tail = node;
		this.length++;
		return true;
	}
	
	// 出队操作，复杂度是 O(1)
	public Object dequeue() {
		if (this.isEmpty()) {
			return null;
		}
		Node nextNode = this.head.next;
		Object ret = this.head.data;
		this.head.data = null;
		this.head.next = null;
		this.head = nextNode;
		if (nextNode == null) {
			this.tail = null;
		}
		this.length--;
		return ret;
	}
	
	public boolean isEmpty() {	
		return this.length == 0;
	}

	public boolean isFull() {
		return this.presetLength == this.length;
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(getClass().getSimpleName()).append(" [");
		Node p = this.head;
		while (p != null) {
			if (p != this.head) {
				stringBuilder.append("->");
			}
			stringBuilder.append(p.data);
			p = p.next;
		}
		stringBuilder.append(']');
		return stringBuilder.toString();
	}

	public static void main(String[] args) {
		IQueue queue = new LinkedQueue(3);
		System.out.println(queue.enqueue(1));
		System.out.println(queue.enqueue(2));
		System.out.println(queue.enqueue(3));
		System.out.println(queue.enqueue(5));
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.enqueue(7));
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);
		
		System.out.println(queue.dequeue());
		System.out.println(queue);
		
		System.out.println(queue.dequeue());
		System.out.println(queue);
		
		System.out.println(queue.enqueue(8));
		System.out.println(queue);
	}
}
